package 力扣.链表;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 合并k个有序链表23 {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {//小根堆
                return o1.val - o2.val;
            }
        });
        for (ListNode list: lists) {
            while (list != null){
                 pq.offer(list);
                 list = list.next;
            }
        }
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!pq.isEmpty()){
            tail.next =  pq.poll();
            tail = tail.next;
        }
        tail.next = null;
        return dummy.next;
    }
    public ListNode mergeKLists2(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {//小根堆
                return o1.val - o2.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            ListNode te = lists[i];
            if (te != null){
                pq.offer(te);
            }
        }
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!pq.isEmpty()){
            ListNode te = pq.poll();
            tail.next = te;
            tail = tail.next;
            if (te.next != null){
                pq.offer(te.next);
            }
        }
        tail.next = null;
        return dummy.next;
    }
}
